def exgcd(a,b):
    if b==0:
        return a,1,0
    g,x2,y2= exgcd(b,a%b)
    x1,y1=y2,x2-(a//b)*y2
    return g,x1,y1

# 求解ax+by=m  的一组解
def Func(a,b,m):
    g,x1,y1 = exgcd(a,b)
    if m%g!=0:
        return None,None,None
    x0,y0=x1*m//g,y1*m//g
    return g,x0,y0

# 求a在模n意义下的逆元x，即ax=1 mod n
# 即ax+ny=1
def Inv(a,n):
    g,x,y = Func(a,n,1)
    if x is None:
        return None
    else:
        return (x%n+n)%n

a,b=map(int,input().split())
print(Inv(a,b))
